This invention relates generally to compression of binary images, and more particularly to the lossless precompression of binary images that are to be stored or transmitted at high resolutions.
A portion of the disclosure of this patent document contains material which is subject to copyright protection. The copyright owner has no objection to the facsimile reproduction by anyone of the patent document or the patent disclosure, as it appears in the Patent and Trademark Office patent file or records, but otherwise reserves all copyright rights whatsoever.
The present invention is related to the lossless precompression of binary images that are to be stored or transmitted at high resolutions. More specifically, the present invention employs an area-based compression technique that is appropriate for high resolution bit replicated images. The technique searches for regularly sized image regions of a common color and represents the areas in a coded fashion. The compression technique employed by the present invention enables high resolution images to be compressed and stored or transmitted at an image size approximating the size of an image typically obtained by lossless compression of the original bitmap binary image from which the high resolution image was generated. While most applicable to binary images, the technique can be applied to multiple bit per pixel gray scale images by treating each plane of individual bits as a binary image.
In many digital printing architectures (including printers, copiers, and multifunction machines) it is necessary to store precollated images in memory so that such images may be accessed and printed at a high bandwidth. This is opposed to the well-known practice of composing/collating the image xe2x80x9con-the-flyxe2x80x9d which tends to result in slower printing speeds or the need for higher-speed hardware. However, there are drawbacks associated with the storage of image bitmaps in memory, hereafter referred to as electronic precollation memory (EPC). The primary drawback is that the size of the memory must be significant in order to store even moderate resolution images. For example, a full page binary image bitmap at 300 spots per inch (spi) requires approximately 1.05 megabytes (MB) of memory. The problem is only exacerbated by higher resolution printers. A 1200 spi printer will require approximately 16.83 MB to store the same image at the higher resolution. Thus, it is apparent that as the resolution of digital printers increases, there is an ever-growing need for improved compression techniques to reduce precollation memory requirements.
Heretofore, a number of patents and publications have disclosed compression techniques, the relevant portions of which may be briefly summarized as follows:
U.S. Pat. No. 5,144,682 to Nakamura, issued Sep. 1, 1992, discloses a method and apparatus for isolating an area corresponding to a character or word. Included therein is a compression treatment section for compressing the data of the original manuscript in a direction corresponding to that of the manuscript""s character line and a compressed image buffer (a ring buffer) for storing the image data. The compression section performs an OR logic operation to accomplish proportional compression. Also described are thresholding and thinning compression methods. The area of connected picture elements is determined by a contour following operation (col. 4-5 and FIG. 4). A rectangular area having an apex of the minimum main and subscanning addresses and another opposing apex of the maximum main and subscanning addresses is then extracted. However, this area is merely a representation of an area within the compressed image (col. 6, lines 1-7).
U.S. Pat. No. 5,204,756 to Chevion et al., issued Apr. 20, 1993, teaches a method for the compression and decompression of binary images. The invention accomplishes variable compression ratios through the use of lossy and lossless compression techniques, selected based upon an evaluation of the binary image at hand. After evaluating the image by dividing it into mutually exclusive segments (e.g., image or text segments), a raster-based compression technique is selected based upon the type of the image segment. The selection (determined by a compression ratio) is further influenced by a metric characterized as the relative widths of black or white intervals in the original text image.
U.S. Pat. No. 5,363,205 to Shou et al., issued Nov. 8, 1994, teaches an image compression method which successively diminishes in size the image to form a compressed image. In particular, a gray scale image is successively reduced by representing a 2xc3x972 convolution by a pixel of its mean density.
J. Murray and W. vanRyper, in xe2x80x9cEncyclopedia of Graphic File Formats,xe2x80x9d O""Reilly and Assoc., July 1994, pp. 125-171 describe details of various publicly known data compression schemes. The publication is hereby incorporated by reference for its teachings relating to compression terminology and compression schemes.
D. Moitra, in xe2x80x9cFinding a Minimal Cover for Binary Images: An Optimal Parallel Algorithm,xe2x80x9d published Nov. 1, 1988 (Cornell University, Computer Science Department), teaches an algorithm for determining a minimal set of maximal squares to cover a binary image. The minimal set of black subsquares is intended to cover the black regions of the image using a set of overlapping squares. Described further is a cover graph which compactly represents the covering relationships between the squares.
In accordance with the present invention, there is provided a method, operating in an image processing system, for compressing a binary input image where the binary input image is represented as a regular array of binary image signals, comprising the steps of:
identifying an orthogonally shaped, two-dimensional region of binary image signals having a common state;
determining the size of the orthogonally shaped region;
encoding the state and size of the orthogonally shaped region as a digital data word;
storing the digital data word representing the encoded shape and size in compression memory; and
repeating the above steps for each of a plurality of orthogonally shaped regions of binary image signals present within the binary input image.
In accordance with another aspect of the present invention, there is provided an image processing system, comprising:
image data memory for storing binary image signals;
a processor, operating in response to a set of preprogrammed instructions, for identifying an orthogonally shaped, two-dimensional region of binary image signals having a common state, said processor further determining the size of the orthogonally shaped, two-dimensional region, encoding the state and size of the orthogonally shaped region as a digital data word, and outputting the encoded digital data word;
a lossless data compressor, responsive to the digital data word output by the processor, for applying lossless compression to the digital data word to produce compressed data therefrom; and
precollation memory for storing the compressed data produced by the lossless data compressor.
In accordance with yet another aspect of the present invention, there is provided a method, operating in an image processing system, for compressing a binary input image where the binary input image is represented as a regular array of binary image signals, comprising the steps of:
(a) identifying an orthogonally shaped, two-dimensional region of binary image signals having a common state;
(b) determining the size of the orthogonally shaped region;
(c) encoding the state and size of the orthogonally shaped region as a digital data word;
(d) storing the digital data word representing the encoded shape and size in compression memory;
(e) repeating the above steps for each of a plurality of orthogonally shaped regions of binary image signals present within the binary input image to produce a precompressed image; and
(f) losslessly compressing the precompressed image to produce a compressed image.
One aspect of the invention deals with a basic problem in image processing, that of storing and transmitting images. This problem has been recognized and various compression techniques have been employed. However, such techniques are typically raster-based.
This aspect is further based on the discovery of a technique that removes constraints associated with raster-based techniques. The technique employed herein is two-dimensional, dividing the high resolution image into orthogonal blocks of a common color or binary state and then encoding the image information by recording the image as a series of data words having N bits (where N is a power of 2), each word containing bits to represent the color/state and size of the orthogonal blocks.
The technique described herein is advantageous because when compared to other approaches and the technique makes it largely unnecessary to employ a large precollation memory in an image processing system, for example a system associated with a digital printer. In addition, it can be used to compress images prior to transmission thereof. The precompression and de-precompression techniques of the invention are advantageous because they permit efficient compression and decompression of bitmap images. In addition, the techniques that form the basis of this invention can be used in combination with other lossless compression techniques to further improve the compression ratios achieved by the invention. As a result of the invention, it is possible to reduce the size or precollation memory in a digital printer, or to increase the number of images stored therein.